/**************************************************************************
*   Copyright (C) 2010 Chernov Dmitry                                     *
*                                                                         *
*   This program is free software; you can redistribute it and/or modify  *
*   it under the terms of the GNU General Public License as published by  *
*   the Free Software Foundation; either version 2 of the License, or     *
*   (at your option) any later version.                                   *
*                                                                         *
*   This program is distributed in the hope that it will be useful,       *
*   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
*   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
*   GNU General Public License for more details.                          *
*                                                                         *
*   You should have received a copy of the GNU General Public License     *
*   along with this program; if not, write to the                         *
*   Free Software Foundation, Inc.,                                       *
*   59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.             *
***************************************************************************/

#include "MarbleGameSolver.h"

#include <iostream>


MarbleGameSolver::MarbleGameSolver( int threadCount ) : m_threadCount(threadCount),
                                                        m_isDestroying(false),
                                                        m_started(false)
{
    if( m_threadCount > 0 )
    {
        InitializeCriticalSection( &m_saveCS );
        InitializeCriticalSection( &m_poolCS );
        InitializeCriticalSection( &m_taskCS );
        spawnThreads();
    }
}

MarbleGameSolver::~MarbleGameSolver()
{
    DeleteCriticalSection( &m_saveCS );
    DeleteCriticalSection( &m_poolCS );
    DeleteCriticalSection( &m_taskCS );
        
    if( m_threadCount > 0 )
        destroyThreads();
}

std::string MarbleGameSolver::findShortestSolution( const std::string& task )
{
    m_shortestNow.clear();

    MarbleTask gm( task, this );

    try
    {
        gm.solve();
    }
    catch( std::exception ex )
    {
        std::cout << "exception while solving task" << std::endl;
    }

    if( m_threadCount > 0 )
    {
        // Wait while all the work is done
        do
        {
            Sleep(10);
        } while( stillUndone() );
    }

    return m_shortestNow;
}

void MarbleGameSolver::saveSolution( const std::vector<MarbleTask::direction> &sol )
{
    if( m_threadCount > 0 )
        EnterCriticalSection( &m_saveCS );

    size_t size = sol.size();

    if( m_shortestNow.empty() || size < m_shortestNow.size() )
    {
        m_shortestNow.clear();

        // Save soluttion in human readable form
        for( size_t i = 0; i < sol.size(); i++ )
        {
            if( sol[i] == MarbleTask::up )
                m_shortestNow += 'S';
            else if( sol[i] == MarbleTask::right )
                m_shortestNow += 'W';
            else if( sol[i] == MarbleTask::down )
                m_shortestNow += 'N';
            else if( sol[i] == MarbleTask::left )
                m_shortestNow += 'E';
        }
    }

    if( m_threadCount > 0 )
        LeaveCriticalSection( &m_saveCS );
}

DWORD WINAPI MarbleGameSolver::threadProc(LPVOID pParam)
{
    if( NULL == pParam )
        return -1;

    HANDLE hWaits[2];
    DWORD threadId = GetCurrentThreadId();

    MarbleGameSolver* pool = static_cast<MarbleGameSolver*>(pParam);
    hWaits[0] = pool->getWaitHandle(threadId);
    hWaits[1] = pool->getShutdownHandle();

    while(1)
    {
        DWORD res = WaitForMultipleObjects( 2, hWaits, FALSE, INFINITE );

        if( res - WAIT_OBJECT_0 == 1 )
            return 0;   // Shutdown event notification

        if( pool->checkThreadStop() )
            return 0;

        ResetEvent( hWaits[0] );

        pool->tryRunTask();
        pool->finishNotify( threadId );
    }

    return 0;
}

bool MarbleGameSolver::spawnThreads()
{
    HANDLE hThread;
    DWORD threadId;
    ThreadData threadData;

    // Create the event which will signal the threads to stop
    m_notifyShutdown = CreateEvent( NULL, TRUE, FALSE, NULL );

    if( !m_notifyShutdown )
    {
        std::cout << "problem creating shutdown notify event" << std::endl;
        m_threadCount = 0;
        return false;
    }

    // Create the threads
    for( int i = 0; i < m_threadCount; ++i )
    {
        hThread = CreateThread( NULL, 0, MarbleGameSolver::threadProc,
                                this, CREATE_SUSPENDED, &threadId );

        if( hThread )
        {
            // Add the entry to the map of threads
            threadData.m_free = true;
            threadData.m_waitHandle = CreateEvent( NULL, TRUE, FALSE, NULL );
            threadData.m_thread = hThread;
            threadData.m_threadId = threadId;

            m_threads.insert( ThreadMap::value_type( threadId, threadData ) );

            ResumeThread( hThread );
        }
        else
        {
            std::cout << "can't spawn " << i << " thread" << std::endl;
            m_threadCount = i - 1;
            return false;
        }
    }

    return true;
}

void MarbleGameSolver::destroyThreads()
{
    // Set the state to 'destroying'. Pooled functions might be checking this
    // state to see if they need to stop.
    m_isDestroying = true;

    // Tell all threads to shutdown.
    SetEvent( m_notifyShutdown );

    Sleep( THREAD_WAIT_INTERVAL ); // Give the threads a chance to complete

    if( getWorkingThreadCount() > 0 )
    {
        // There are still threads in processing mode..
        // lets give em one last chance to finish based on configured setting
        Sleep( THREAD_WAIT_INTERVAL*3 );
    }

    ThreadMap::iterator iter;
    ThreadData threadData;

    // Walk through the events and threads and close them all
    for( iter = m_threads.begin(); iter != m_threads.end(); ++iter )
    {
        threadData = (*iter).second;
        CloseHandle( threadData.m_waitHandle );
        CloseHandle( threadData.m_thread );
    }

    CloseHandle( m_notifyShutdown );
    m_notifyShutdown = NULL;

    m_threads.clear();
}

HANDLE MarbleGameSolver::getWaitHandle( DWORD threadId )
{
    HANDLE hWait;
    ThreadMap::iterator iter;

    EnterCriticalSection( &m_poolCS );
    iter = m_threads.find( threadId );

    if( iter == m_threads.end() )   // If search found no elements
    {
        LeaveCriticalSection( &m_poolCS );
        return NULL;
    }
    else
    {
        hWait = m_threads[threadId].m_waitHandle;
        LeaveCriticalSection( &m_poolCS );
    }

    return hWait;
}

HANDLE MarbleGameSolver::getShutdownHandle()
{
    return m_notifyShutdown;
}

bool MarbleGameSolver::checkThreadStop()
{
    // This is function expected to be called by thread functions
    // The expectation is that threads will check this and stop.
    return m_isDestroying;
}

void MarbleGameSolver::finishNotify( DWORD threadId )
{
    ThreadMap::iterator iter;

    EnterCriticalSection( &m_poolCS );
    iter = m_threads.find( threadId );

    if( iter == m_threads.end() )   // If search found no elements
    {
        std::cout << "no thread with id = " << threadId << std::endl;
        LeaveCriticalSection( &m_poolCS );
    }
    else
    {
        m_threads[threadId].m_free = true;
        LeaveCriticalSection( &m_poolCS );
    }

    start();
}

int MarbleGameSolver::getWorkingThreadCount()
{
    ThreadMap::iterator iter;
    ThreadData threadData;

    int nCount = 0;

    for( iter = m_threads.begin(); iter != m_threads.end(); iter++ )
    {
        threadData = (*iter).second;

        if( !threadData.m_free )
        {
            nCount++;
        }
    }

    return nCount;
}

bool MarbleGameSolver::freeThreadsPresent()
{
    if( m_threadCount == 0 )
        return false;

    // Find out if there are any idle threads
    return ( m_threadCount - getWorkingThreadCount() ) > 0;
}

void MarbleGameSolver::addMarbleTask( MarbleTask *gm )
{
    // Here we make a copy of marble task and put
    // it into the queue of tasks
    EnterCriticalSection( &m_taskCS );
    m_taskQueue.push_back( *gm );
    LeaveCriticalSection( &m_taskCS );

    start();
}

void MarbleGameSolver::tryRunTask()
{
    MarbleTask task;

    EnterCriticalSection( &m_taskCS );
    if( m_taskQueue.size() > 0 )
    {
        task = m_taskQueue.front();
        m_taskQueue.pop_front();
    }
    LeaveCriticalSection( &m_taskCS );

    if( task.m_initialized )
        task.solve();
}

void MarbleGameSolver::start()
{
    int threadsToStart = 0;

    EnterCriticalSection( &m_taskCS );
    threadsToStart = m_taskQueue.size();
    LeaveCriticalSection( &m_taskCS );

    if( threadsToStart == 0 )
        return;

    ThreadMap::iterator iter;
    ThreadData threadData;

    // Set events which hold threads in wait state
    EnterCriticalSection( &m_poolCS );
    for( iter = m_threads.begin(); iter != m_threads.end(); ++iter )
    {
        threadData = (*iter).second;

        if( threadData.m_free )
        {
            threadData.m_free = false;
            SetEvent( threadData.m_waitHandle );
            threadsToStart--;

            if( threadsToStart == 0 )
                break;
        }
    }
    LeaveCriticalSection( &m_poolCS );
}

bool MarbleGameSolver::stillUndone()
{
    if( getWorkingThreadCount() > 0 )
        return true;

    bool ret = false;
    EnterCriticalSection( &m_taskCS );
        ret = ( m_taskQueue.size() > 0 );
    LeaveCriticalSection( &m_taskCS );

    return ret;
}

int MarbleGameSolver::yetShortestSol()
{
    int ret = MarbleTask::MAX_DEPTH_DEFAULT;

    if( m_threadCount > 0 )
        EnterCriticalSection( &m_saveCS );
    int length = m_shortestNow.length();
    if( length > 0 )
        ret = length;

    if( m_threadCount > 0 )
        LeaveCriticalSection( &m_saveCS );
    return ret;
}
